1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5 + 5;
using namespace std;
struct T{
struct A{
int l, r;
LL Minl, Minr, tg;
}a[maxn << 2];
void build(int cur, int l, int r){
a[cur].l = l, a[cur].r = r;
if (l == r){
a[cur].Minl = INF;
a[cur].Minr = INF;
a[cur].tg = 0;
return;
} int mid = l + r >> 1;
build(cur << 1, l, mid); build(cur << 1 | 1, mid + 1, r);
a[cur].Minl = min(a[cur << 1].Minl, a[cur << 1 | 1].Minl);
a[cur].Minr = min(a[cur << 1].Minr, a[cur << 1 | 1].Minr);
}
void pushdown(int cur){
if (a[cur].tg == 0) return;
a[cur << 1].tg += a[cur].tg;
a[cur << 1].Minl += a[cur].tg;
a[cur << 1].Minr += a[cur].tg;
a[cur << 1 | 1].tg += a[cur].tg;
a[cur << 1 | 1].Minl += a[cur].tg;
a[cur << 1 | 1].Minr += a[cur].tg;
a[cur].tg = 0;
}
LL Query(int cur, int p){
if (a[cur].l == a[cur].r) return a[cur].Minl + a[cur].l;
pushdown(cur);
int mid = a[cur].l + a[cur].r >> 1;
if (p <= mid) return Query(cur << 1, p);
return Query(cur << 1 | 1, p);
}
LL QMinl(int cur, int l, int r){
if (a[cur].l > r || a[cur].r < l) return INF;
if (a[cur].l >= l && a[cur].r <= r) return a[cur].Minl;
pushdown(cur);
return min(QMinl(cur << 1, l, r), QMinl(cur << 1 | 1, l, r));
}
LL QMinr(int cur, int l, int r){
if (a[cur].l > r || a[cur].r < l) return INF;
if (a[cur].l >= l && a[cur].r <= r) return a[cur].Minr;
pushdown(cur);
return min(QMinr(cur << 1, l, r), QMinr(cur << 1 | 1, l, r));
}
void upd(int cur, int p, LL k){
if (a[cur].l == a[cur].r){
a[cur].Minl = min(a[cur].Minl, k - p);
a[cur].Minr = min(a[cur].Minr, k + p);
return;
}
pushdown(cur);
int mid = a[cur].l + a[cur].r >> 1;
if (p <= mid) upd(cur << 1, p, k);
else upd(cur << 1 | 1, p, k);
a[cur].Minl = min(a[cur << 1].Minl, a[cur << 1 | 1].Minl);
a[cur].Minr = min(a[cur << 1].Minr, a[cur << 1 | 1].Minr);
}
}t;
int n, A, B, Q;
LL x[maxn];
LL _abs(LL x){return x < 0 ? -x : x;}
int main(){
scanf("%d%d%d%d", &n, &Q, &A, &B);
for (int i = 1; i <= Q; i++) scanf("%lld", x + i);
t.build(1, 1, n); t.upd(1, A, _abs(1ll * B - x[1])); t.upd(1, B, _abs(1ll * A - x[1]));
for (int i = 2; i <= Q; i++){
LL d = _abs(x[i] - x[i - 1]), tmp = t.Query(1, x[i - 1]);
LL Minl = t.QMinl(1, 1, x[i]);
LL Minr = t.QMinr(1, x[i], n);
t.a[1].Minl += d;
t.a[1].Minr += d;
t.a[1].tg += d;
t.upd(1, x[i - 1], min(tmp + d, min(Minl + x[i], Minr - x[i])));
} LL ans = INF;
for (int i = 1; i <= n; i++) ans = min(ans, t.Query(1, i));
printf("%lld\n", ans);
return 0;
}
|